'''
有序数组查找指定元素常用二分法
'''


class Solution:
    # 查找具体值 l <= r, r+1,l-1,
    def binarySearch(self, nums, target):
        """
        模板 #1 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板，
        大多数高中或大学会在他们第一次教学生计算机科学时使用。模板 #1 用于查找可以通过访问数组中的单个索引来确定的元素或条件。
        二分查找的最基础和最基本的形式。
        查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
        不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        # End Condition: left > right
        return -1

    # 找索引 l < r, l+1
    def binarySearch_index(self, nums, target):
        """
        模板 #2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

        一种实现二分查找的高级方法。
        查找条件需要访问元素的直接右邻居。
        使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
        保证查找空间在每一步中至少有 2 个元素。
        需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        # Post-processing:
        # End Condition: left == right
        if left != len(nums) and nums[left] == target:
            return left
        return -1

    def binarySearch_3(nums, target):
        """
        模板 #3 是二分查找的另一种独特形式。 它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
        实现二分查找的另一种方法。
        搜索条件需要访问元素的直接左右邻居。
        使用元素的邻居来确定它是向右还是向左。
        保证查找空间在每个步骤中至少有 3 个元素。
        需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。

        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid
            else:
                right = mid

        # Post-processing:
        # End Condition: left + 1 == right
        if nums[left] == target: return left
        if nums[right] == target: return right
        return -1

s = Solution()
print(s.binarySearch_index([4,5,6,7,0,1,2], 3))
